//
// Created by Snow on 2023/3/27.
//
#include<cstdio>
#include<cstdlib>
typedef char ElemType;
typedef struct lnode
{
    int tag;//结点类型标识符
    union
    {
        ElemType data;//存放原子值
        struct lnode *sublist;//指向子表的指针
    }val;
    struct lnode *link;//指向下一个元素
}GLNode;//广义表的数据类型
//求广义表的长度
int GLLength(GLNode *g)
{
    int n=0;//累计元素的个数，初始值为0
    GLNode *g1=g->val.sublist;//g1指向广义表的第一个元素
    while(g1!=nullptr)//扫描所以元素结点
    {
        n++;//元素的个数增一
        g1=g1->link;
    }
    return n;//返回元素的个数
}
//求广义表的深度
int GLDepth(GLNode *g)
{
    GLNode *g1;
    int maxd=0,dep;
    if(g->tag==0)
        return 0;//为原子时返回0
    g1=g->val.sublist;//g1指向第一个元素
    if(g1==nullptr)//为空表时返回1
        return 1;
    while(g1!=nullptr)//遍历表中的每一个元素
    {
        if(g1->tag==1)//元素为子表的情况
        {
            dep=GLDepth(g1);//递归调用求出子表的深度
            if(dep>maxd)//maxd为同一层的子表中深度的最大值
                maxd=dep;
        }
        g1=g1->link;//是g1指向下一个元素
    }
    return(maxd+1);//返回表的深度
}
//输出广义表
void DispGL(GLNode *g)
{
    if(g!=nullptr)//表不为空时判断
    {
        if(g->tag==0)//g的元素为原子时
            printf("%c",g->val.data);//输出原子值
        else//g的元素为子表时
        {
            printf("(");//输出(
            if(g->val.sublist==nullptr)//为空表时
                printf("#");
            else
                DispGL(g->val.sublist);//为非空表时
            printf(")");//输出)
        }
        if(g->link!=nullptr)
        {
            printf(",");
            DispGL(g->link);//递归输出g的兄弟
        }
    }
}
//求原子个数
//1
int Count1(GLNode *g)
{
    int n=0;
    GLNode *g1=g->val.sublist;
    while(g1!=nullptr)
    {
        if(g1->tag==0)
            n++;
        else
            n+= Count1(g1);
        g1=g1->link;
    }
    return n;
}
//2
int Count2(GLNode *g)
{
    int n=0;
    if(g!=nullptr)
    {
        if(g->tag==0)
            n++;
        else
            n+=Count2(g->val.sublist);
        n+=Count2(g->link);
    }
    return n;
}
//创建由括号表示法表示s的广义表链式存储结构
GLNode *CreatGL(char *&s)
{
    GLNode *g;
    char ch=*s++;//取一个字符
    if(ch!='\0')//串未结束判断
    {
        g=(GLNode*)malloc(sizeof(GLNode));//创建一个新结点
        if(ch=='(')//当前字符为左括号时
        {
            g->tag=1;//新结点作为表头结点
            g->val.sublist= CreatGL(s);//递归构造子表并链到表头结点
        }
        else if(ch==')')
            g=nullptr;//遇到')'字符,g置为空
        else if(ch=='#')
            g=nullptr;//遇到'#'字符，表示为空表
        else//为原子字符
        {
            g->tag=0;//新结点作为原子结点
            g->val.data=ch;
        }
    }
    else
        g=nullptr;//串结束,g置为空
    ch=*s++;//取下一个字符
    if(g!=nullptr)//串未结束，继续构造兄递结点
    {
        if(ch==',')//当前字符为','
            g->link= CreatGL(s);//递归构造兄递结点
        else //没有兄弟了,将兄弟指针置为NULL
            g->link=nullptr;
    }
    return g;//返回广义表g
}
void DestroyGL(GLNode *&g)//销毁广义表
{
    GLNode *g1,*g2;
    g1=g->val.sublist;//g1指向广义表的第一个元素
    while(g1!=nullptr)//遍历所有元素
    {
        if(g1->tag==0)//若为原子结点
        {
            g2=g1->link;//g2临时保存兄弟结点
            free(g1);//释放g1所指原子结点
            g1=g2;//g1指向后继兄弟结点
        }
        else//若为子表
        {
            g2=g1->link;//g2临时保存兄弟结点
            DestroyGL(g1);//递归释放g1所指子表的空间
            g1=g2;//g1指向后继兄弟结点
        }
    }
    free(g);//释放头结点空间
}
char Max(GLNode *g)
{
    char max='\0',temp='\0';
    if(g!=nullptr)
    {
        if(g->tag==0)
            max=g->val.data;
        else
        {
            if(g->val.sublist!=nullptr)
                temp=Max(g->val.sublist);
            if(temp>max)max=temp;
        }
        if(g->link!=nullptr)
        {
            temp=Max(g->link);
            if(temp>max)max=temp;
        }
    }
    return max;
}
int main()
{
    char *s="(b,(b,a,(#),d),((a,b),c,((#))))";
    GLNode *g;
    g=CreatGL(s);
    printf("Length=%d\n",GLLength(g));
    printf("Deep=%d\n",GLDepth(g));
    printf("%c\n",Max(g));
    DispGL(g);
    DestroyGL(g);
}